I. Field
The present invention relates to data communication. More particularly, the present invention relates to a novel and improved buffer structure for storing intermediate results for a Turbo decoder.
II. Background
Wireless communication systems are widely deployed to provide various types of communication such as voice, data, and so on. These systems may be based on code division multiple access (CDMA), time division multiple access (TDMA), or some other multiple access techniques. A CDMA system provides certain advantages over other types of system, including increased system capacity.
A CDMA system may be designed to support one or more CDMA standards such as (1) the xe2x80x9cTIA/EIA-95-B Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular Systemxe2x80x9d (the IS-95 standard), (2) the xe2x80x9cTIA/EIA-98-D Recommended Minimum Standard for Dual-Mode Wideband Spread Spectrum Cellular Mobile Stationxe2x80x9d (the IS-98 standard), (3) the standard offered by a consortium named xe2x80x9c3rd Generation Partnership Projectxe2x80x9d (3GPP) and embodied in a set of documents including Document Nos. 3G TS 25.211, 3G TS 25.212, 3G TS 25.213, and 3G TS 25.214 (the W-CDMA standard), (4) the standard offered by a consortium named xe2x80x9c3rd Generation Partnership Project 2xe2x80x9d (3GPP2) and embodied in a set of documents including Document Nos. C.S0002-A, C.S0005-A, C.S0010-A, C.S0011-A. C.S0024, and C.S0026 (the cdma2000 standard), and (5) some other standards. These standards are incorporated herein by reference.
Each standard specifically defines the processing of data for transmission on the forward and reverse links. For example, speech information may be coded at a particular data rate, formatted into a defined frame format, and processed (e.g., encoded for error correction and/or detection, interleaved, and so on) in accordance with a particular processing scheme. The frame formats and processing defined by a particular standard (e.g., cdma2000 standard) are likely to be different from those of other standards (e.g., W-CDMA standard).
The W-CDMA standard supports flexible operation. For example, data may be transmitted in bursts and over one or more xe2x80x9cphysicalxe2x80x9d channels, the data rate may be allowed to vary from frame to frame, the processing of the data may also vary (e.g., from frame to frame and/or from xe2x80x9ctransportxe2x80x9d channel to channel), and so on.
The W-CDMA standard employs a parallel concatenated convolutional encoder (often referred to as a Turbo encoder), which may be selected for encoding a code segment (i.e., a data packet) prior to transmission. The Turbo encoder employs two constituent encoders operated in parallel and in combination with a code interleaver. The code interleaver shuffles (i.e., interleaves) the information bits in the packet in accordance with a specifically defined interleaving scheme. One encoder encodes the information bits in the packet to generate a first sequence of parity bits, and the other encoder encodes the shuffled information bits to generate a second sequence of parity bits. The information bits and all or some of the parity bits in the first and second sequences are transmitted.
Complementary (and computationally intensive) Turbo decoding is performed at a receiver unit. For each Turbo encoded packet, the received bits are stored to a buffer. The information and parity bits for the first encoder are then retrieved from the buffer and decoded based on the first constituent code to provide xe2x80x9cextrinsicxe2x80x9d information indicative of adjustments in the confidence in the detected values for the information bits. Intermediate results that include the extrinsic information from the first decoder are then stored to a storage unit in an interleaved order matching the code interleaving used at the transmitter unit.
The intermediate results and the parity bits from the second encoder are then retrieved from their respective sources and decoded based on the second constituent code to provide extrinsic information indicative of further adjustments in the confidence in the detected values for the information bits. Intermediate results that comprise the extrinsic information from the second decoder are then stored to the storage unit in a deinterleaved order complementary to the code interleaving used at the transmitter unit. The intermediate results are used by the next iteration of the first constituent decoder. The decoding by the first and second constituent decoders is iterated a number of times to yield the final results.
For each information bit to be decoded, the storage unit is accessed to retrieve intermediate result generated for this bit by a prior decoding (if any). The intermediate result generated for each decoded bit is also stored back to the storage unit for use in a subsequent decoding. The storage unit is thus continually accessed as bits in the packet are decoded. Efficient memory management is essential for efficient Turbo decoding.
As can be seen, a buffer structure that may be used to efficiently store intermediate results for a Turbo decoder is highly desirable.
Aspects of the present invention provide a buffer structure that may be used to efficiently store intermediate results (e.g., a priori probability (APP) data) for a Turbo decoder. To increase access throughput of APP data during Turbo decoding, the buffer structure is designed to support concurrent access (i.e., write or read) of APP data for two or more information bits for each access cycle. The APP data for each bit is representative of either a combination of an information bit and its extrinsic information or just the extrinsic information for the bit. The concurrent access can be achieved by partitioning the buffer into a number of banks, with each bank being independently accessible. For example, six or more banks may be used for a Turbo decoder used in a W-CDMA system.
A Turbo encoder employs a code interleaving scheme to shuffle the information bits in a data packet prior to encoding by a second constituent encoder. The code interleaving scheme typically specifies (1) writing the information bits in a data packet (or code segment) row-by-row into a 2-dimensional array, (2) shuffling the elements within each row, and (3) shuffling the rows. The bits are thereafter read column-by-column from the array. The same interleaving scheme and a complementary deinterleaving scheme are used for storing/retrieving the APP data for the Turbo decoder.
For Turbo decoding, the APP data may be accessed via an xe2x80x9cinterleavedxe2x80x9d addressing mode or a xe2x80x9clinearxe2x80x9d addressing mode. The interleaved addressing mode corresponds to access of APP data at xe2x80x9cinterleavedxe2x80x9d locations in a data packet, and the linear addressing mode corresponds to access of APP data at xe2x80x9clinearxe2x80x9d locations in the packet. To avoid access contentions, the banks are assigned to the rows and columns of the array such that APP data for consecutive bits to be (accessed via either linear or interleaved addressing mode) are from different banks.
To ensure that two different banks are accessed for APP data for two consecutive bits in the linear addressing mode, the banks can be arranged and assigned such that one set of banks is used for even-numbered columns of the array, and another set of banks is used for odd-numbered columns. With this odd/even assignment scheme, consecutive linear addresses are associated with two different sets of banks.
To ensure that two different banks are accessed for APP data for two consecutive bits in the interleaved addressing mode, the banks can be assigned to groups of rows in the array. Since the bits for the data packet are retrieved column-by-column from the array in the interleaved addressing mode, the rows can be arranged into groups such that adjacent rows for the interleaved addressing mode are assigned to different groups. The grouping of the rows is typically dependent on the one or more permutation patterns used to shuffle the rows. The row grouping is described in further detail below.
Various aspects, embodiments, and features of the invention are described in further detail below.